package com.wujunshen.algorithm.leetcode.depth.first.search;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/25 17:06<br>
 */
public class 在二叉树中分配硬币 {
  int moves = 0;

  public int distributeCoins(TreeNode1 root) {
    count(root);
    return moves;
  }

  public int count(TreeNode1 node) {
    if (node == null) {
      return 0;
    }
    int countLeft = count(node.left);
    int countRight = count(node.right);
    moves += Math.abs(countLeft) + Math.abs(countRight);
    return countLeft + countRight + node.val - 1;
  }
}
